/**
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * <p>
 * 说明:
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 示例 1:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a*"
 * 输出: true
 * 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 * 示例 3:
 * <p>
 * 输入:
 * s = "ab"
 * p = ".*"
 * 输出: true
 * 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 * 示例 4:
 * <p>
 * 输入:
 * s = "aab"
 * p = "c*a*b"
 * 输出: true
 * 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 * 示例 5:
 * <p>
 * 输入:
 * s = "mississippi"
 * p = "mis*is*p*."
 * 输出: false
 */
class RegularExpression {

    public static void main(String[] args) {
        System.out.println(RegularExpression.isMatch("aa", "a"));//false
        System.out.println(RegularExpression.isMatch("aaa", "aaaa"));//false
        System.out.println(RegularExpression.isMatch("mississippi", "mis*is*p*."));//false
        System.out.println("");
        System.out.println(RegularExpression.isMatch("aa", "a*"));///true
        System.out.println(RegularExpression.isMatch("ab", ".*"));//true
        System.out.println(RegularExpression.isMatch("aab", "c*a*b"));//true
        System.out.println(RegularExpression.isMatch("aaa", "a*a"));//true
        System.out.println(RegularExpression.isMatch("a", "ab*"));//true

        System.out.println("");

        System.out.println(RegularExpression.isMatch("aba", ".*b"));//false
        System.out.println(RegularExpression.isMatch("aba", ".*ab"));//false
        System.out.println(RegularExpression.isMatch("ab", ".*c"));//false
        System.out.println("");
        System.out.println(RegularExpression.isMatch("aba", ".*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*b.*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*ba"));//true
        System.out.println(RegularExpression.isMatch("abab", ".*ab"));//true


    }

    /**
     * 用递归的方法去处理这个（以汉诺塔的形式，我不需要考虑每次递归之后怎么处理，我把可能的情况罗列处理，任意一种满足就是匹配到了）
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        return isMatch(s.toCharArray(), p.toCharArray(), 0, 0);
    }

    public static boolean isMatch(char[] s, char[] p, int x, int y) {
        //如果两个字符串都到了最后，则匹配成功
        if (s.length == x && p.length == y) return true;

        //如果一个结束了另外一个还没结束，则匹配失败
        if (s.length < x || p.length == y) return false;

        //如果p已经是最后一个了
        if (p.length == y + 1) {
            if (p[y] == '.') return s.length == x + 1;
            else return s.length == x + 1 && s[x] == p[y];
        }

        //如果都没结束则继续用匹配
        if (p[y] == '.') {
            if (p[y + 1] == '*') {
                //如果p匹配到了.*,如果有三种情况，x不变，y+2 | x+1，y不变 | x+1，y+2
                return isMatch(s, p, x, y + 2) || isMatch(s, p, x + 1, y) || isMatch(s, p, x + 1, y + 2);
            } else {
                return isMatch(s, p, x + 1, y + 1);
            }
        } else {
            if (p[y + 1] == '*') {
                if (s.length >= x + 1 && s[x] == p[y]) {
                    //如果p匹配到了某字母*,如果有3种情况，x+1，y不变 | x不变，y+2 | x+1，y+2
                    return isMatch(s, p, x + 1, y) || isMatch(s, p, x, y + 2) || isMatch(s, p, x + 1, y + 2);
                } else {
                    return isMatch(s, p, x, y + 2);
                }
            } else {
                if (s.length >= x + 1 && s[x] == p[y]) {
                    return isMatch(s, p, x + 1, y + 1);
                } else {
                    return false;
                }
            }
        }
    }


}